#include "tree.h"

/*
uint GetDigitCount(uint value) {
    return (uint) log10(value);
}

uint GetDigit(uint Number, uint iDigit) {
    Number = iDigit ? (Number / 10 / (iDigit)) : Number;
    return Number - (uint)(((uint) Number *0.1) * 10);
}

 **/

uint GetLeftDigit(uint value) {
    return value - ((uint)((uint) value * 0.1) * 10);
}

uint IsEmptyArray(LPTree *array) {
    uint empty = 1;
    int i;
    for (i = 0; i < 10; i++)
        if (array[i]) empty = 0;
    return empty;
}

LPTree GoToNode(LPTree root, uint value, int AddSubTree) {
    //Рекурсивно ищём узел необходимый для нашего значения
    if (value) {
        //идем в поддерево
        uint NextValue = (uint) value * 0.1;
        uint iSubTree = GetLeftDigit(value);
        //Если поддерево ещё не существует, создаём его
        if (!root->SubTree[iSubTree]) {
            if (AddSubTree) {
                (root)->SubTree[iSubTree] = (LPTree) malloc(sizeof(Tree));
                memset((root)->SubTree[iSubTree]->SubTree, 0, sizeof(LPTree)*10);
                root->SubTree[iSubTree]->Owner = 0;
                (root)->SubTree[iSubTree]->Root = root;
            } else {
                return 0;
            }
        }
        return GoToNode(root->SubTree[iSubTree], NextValue, AddSubTree);
    } else {
        return root;
    }
}

LPTree tree_create() {
    LPTree root = (LPTree) malloc(sizeof(Tree));
    if (!root) return 0;
    memset(root->SubTree, 0, sizeof(LPTree)*10);
    root->Owner = 0;
    root->Root = 0;
    return root;
}

int tree_add(LPTree root, uint value, void* Owner) {
    root = GoToNode(root, value, 1);
    //Проверяем владельца и добавляем узел
    if (root->Owner == 0) {
        (root)->Owner = Owner;
        return TA_OK;
    } else {
        if ((root)->Owner == Owner) {
            return TA_YOUR_REG;
        } else {
            return TA_NOT_YOUR_REG;
        }
    }
}

int tree_del(LPTree root, uint value, void* Owner) {
    root = GoToNode(root, value, 0);
    //если требуемый узел не сущетсвует, выходим
    if (!root) return -1;
    //если узел найден, удаляем его и оптимизируем дерево
    //удаляем узел
    root->Owner = 0;
    //оптимизируем дерево
    while (IsEmptyArray(root->SubTree) && !root->Owner && root->Root) {
        //определяем индекс текущего поддерева для корня
        int i;
        for (i = 0; i < 10; i++)
            if (root->Root->SubTree[i] == root) break;
        //переходим к корню
        root = root->Root;
        //удаляем текущее поддерево из дерева
        free(root->SubTree[i]);
        root->SubTree[i] = 0;
    }
}

int tree_check(LPTree root, uint value, void* Owner) {
    root = GoToNode(root, value, 0);
    if (!root) return 0;
    if (root->Owner == Owner) return 1;
    if (root->Owner != Owner) return 2;
}